<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Automatic Garbage Collection
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora085.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora087.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Automatic Garbage Collection</H2>
<A NAME="@concepts188"></A>
<A NAME="@concepts189"></A>
<A NAME="@concepts190"></A>
We classify automatic memory reclamation algorithms into two classes:
<UL>
<LI>
 reference counters: each allocated region knows how many
 references there are to it. When this number becomes zero, the region
 is freed.

<LI> sweep algorithms: starting from a set of roots,
 the collection of all accessible values is traversed in a way similar
 to the traversal of a directed graph.
</UL>
Sweep algorithms are more commonly used in programming languages.
In effect, reference counting garbage collectors
increase the processing costs (through counter updating) even when there is no need to reclaim
anything.<BR>
<BR>
<A NAME="toc116"></A>
<H3> Reference Counting</H3>
Each allocated region (object) is given a counter. This counter indicates the
number of pointers to the object. It is incremented each time a
reference to the object is shared. It is decremented whenever a pointer
to the object disappears. When the counter becomes zero, the object is
garbage collected.<BR>
<BR>
The advantage of such a system comes from the immediate freeing of
regions that are no longer used. Aside from the systematic slowdown of
computations, reference counting garbage collectors suffer from another
disadvantage: they do not know how to process circular objects.
Suppose that Objective CAML had such a mechanism.
The following example constructs a temporary value <TT>l</TT>, a list of
characters of where the last element points to the cell containing
<CODE>'c'</CODE>. This is clearly a circular value
(figure <A HREF="book-ora086.html#fig-repr1-2">9.2</A>).


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>'c'</CODE>::<CODE>'a'</CODE>::<CODE>'m'</CODE>::l<CODE> </CODE><B>in</B><CODE> </CODE>List.hd<CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>- : char = 'c'</CODE><BR>

</PRE>

<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora031.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.2: Memory representation of a circular list.</DIV><BR>

<A NAME="fig-repr1-2"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
At the end of the calculation of this expression each element of the
list <TT>l</TT> has a counter equal to one (even the first element, for
the tail points to the head).
This value is no longer accessible and yet cannot be reclaimed because
its reference counter is not zero.
In languages equipped with memory reclamation via reference counting---such
as Python---and which allow the construction of circular
values, it is necessary to add a memory sweep algorithm.<BR>
<BR>
<A NAME="toc117"></A>
<H3> Sweep Algorithms</H3>
Sweep algorithms allow us to explore the graph of accessible values on
the heap. This exploration uses a set of roots indicating the beginning
of the traversal. These roots are exterior to the heap, stored most
often in a stack.
In the example in figure <A HREF="book-ora085.html#fig-repr1">9.1</A>, we can suppose that the values
of <TT>u</TT> and <TT>v</TT> are roots. The traversal
starting from these roots constructs the graph of the values to save:
the cells and pointers marked with heavy lines
in figure <A HREF="book-ora086.html#fig-repr2">9.3</A>.
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora032.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.3: Memory reclamation after a garbage collection.</DIV><BR>

<A NAME="fig-repr2"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE><A NAME="@concepts191"></A>The traversal of this graph necessitates knowing how to distinguish
immediate values from pointers in the heap. If a root points to an
integer, we must not consider this value to be the address of another
cell. In functional languages, this distinction is made by using a few
bits of each cell of the heap. We call these bits tag bits<A NAME="GC-bdt"></A>.
This is why Objective CAML integers only use 31 bits.
This option is described in Chapter <A HREF="index.html#chap-IC">12</A>, page <A HREF="book-ora115.html#sec-acces-imm">??</A>.
We describe other solutions to the problem of distinguishing between
pointers and immediate values in this chapter, 
page&nbsp;<A HREF="book-ora086.html#sec-rac-ambig">??</A>.<BR>
<BR>
The two most commonly used algorithms are <I>Mark</I>&amp;<I>Sweep</I>, which constructs the
list of the free cells in the heap, and <I>Stop</I>&amp;<I>Copy</I>, which copies cells that
are still alive to a second memory region.<BR>
<BR>
The heap should be seen as a vector of memory boxes. The representation
of the state of the heap for the example of figure&nbsp;<A HREF="book-ora085.html#fig-repr1">9.1</A>
is illustrated in figure&nbsp;<A HREF="book-ora086.html#fig-repr3">9.4</A>.
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora033.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.4: State of the heap.</DIV><BR>

<A NAME="fig-repr3"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>We use the following characteristics to evaluate a sweep algorithm:
<UL>
<LI>
 efficiency: does the time-complexity depend on the size of the
 heap or only on the number of the living cells?

<LI> reclamation factor: is all of the free memory usable?

<LI> compactness: is all of the free memory usable in a single block?

<LI> localization: are all of the different cells of a structured value
 close to one another?

<LI> memory needs: does the algorithm need to use part of the memory
 when it runs?

<LI> relocation: do values change location following a garbage collection?
</UL>
Localization avoids changing memory pages when traversing a structured
value. Compactness avoids fragmentation of the heap and allows
allocations equal to the amount of available memory. The efficiency,
reclamation factor, and supplementary memory needs are intimately
linked to the time and space complexity of the algorithm.<BR>
<BR>
<A NAME="toc118"></A>
<H3> <I>Mark</I>&amp;<I>Sweep</I></H3>
<A NAME="@concepts192"></A>
<A NAME="@concepts193"></A>
<A NAME="GC-mark-sweep"></A>
The idea of <I>Mark</I>&amp;<I>Sweep</I> is to keep an up-to-date list of the free cells in the
heap called the free list. If, at the time of an allocation request,
the list is empty or no longer contains a free cell of a sufficient
size, then a <I>Mark</I>&amp;<I>Sweep</I> occurs.<BR>
<BR>
It proceeds in two stages:
<OL type=1>
<LI>
 the marking of the memory regions in use, starting from a set of
 roots (called the <I>Mark</I> phase); then

<LI> reclamation of the unmarked memory regions by sequentially sweeping
 through the whole heap (called the <I>Sweep</I> phase).
</OL>
One can illustrate the memory management of <I>Mark</I>&amp;<I>Sweep</I> by using four
``colorings'' of the heap cells: white, gray<A NAME="text20" HREF="book-ora093.html#note20"><SUP><FONT SIZE=2>1</FONT></SUP></A>, black, and hached.
The mark phase uses the gray; the sweep phase, the hached; and the
allocation phase, the white.<BR>
<BR>
The meaning of the gray and black used by marking is as follows:
<UL>
<LI>
 gray: marked cells whose descendents are not yet marked;

<LI> black: marked cells whose descendents are also marked.
</UL>
It is necessary to keep the collection of grayed cells in order to be
sure that everything has been explored. At the end of the marking each
cell is either white or black, with black cells being those that were
reached from the roots. Figure&nbsp;<A HREF="book-ora086.html#fig-msm">9.5</A> shows an intermediate
marking stage for the example of figure&nbsp;<A HREF="book-ora086.html#fig-repr3">9.4</A>: the root
<TT>u</TT> has been swept, and the sweeping of&nbsp;<TT>v</TT> is about to begin.
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora034.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.5: Marking phase.</DIV><BR>

<A NAME="fig-msm"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>It's during the sweep phase that the free list is constructed. The
sweep phase modifies the colorings as follows:
<UL>
<LI>
 black becomes white, as the cell is alive;

<LI> white becomes hached, and the cell is added to the free list.
</UL>
Figure&nbsp;<A HREF="book-ora086.html#fig-mss">9.6</A> shows the evolution of the
colors and the construction of the free list.
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora035.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.6: Sweep phase.</DIV><BR>

<A NAME="fig-mss"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>Characteristics of <I>Mark</I>&amp;<I>Sweep</I> are that it:
<UL>
<LI>
 depends on the size of the entire heap (<I>Sweep</I> phase);

<LI> reclaims all possible memory;

<LI> does not compact memory;

<LI> does not guarantee localization;

<LI> does not relocate data.
</UL>
The marking phase is generally implemented by a recursive function, and
therefore uses space on the execution stack. One can give a completely
iterative version of <I>Mark</I>&amp;<I>Sweep</I> that does not require a stack of indefinite
size, but it turns out to be less efficient than the partially recursive
version.<BR>
<BR>
Finally, <I>Mark</I>&amp;<I>Sweep</I> needs to know the size of values. The size is either
encoded in the values themselves, or deduced from the memory address by
splitting the heap into regions that allocate objects of a bounded
size. The <I>Mark</I>&amp;<I>Sweep</I> algorithm, implemented since the very first versions of
Lisp, is still widely used. A part of the Objective CAML garbage collector
uses this algorithm.<BR>
<BR>
<A NAME="toc119"></A>
<H3> <I>Stop</I>&amp;<I>Copy</I></H3>
<A NAME="@concepts194"></A>
 <A NAME="@concepts195"></A>
<A NAME="subsec-stopcopy"></A>
The principal idea of this garbage collector is to use a secondary
memory in order to copy and compact the memory regions to be saved. The
heap is divided into two parts: the useful part (called <I>from-space</I>), and the part being re-written (called <I>to-space</I>).<BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora036.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.7: Beginning of <I>Stop</I>&amp;<I>Copy</I>.</DIV><BR>

<A NAME="fig-sc-debut"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>The algorithm is the following.
Beginning from a set of roots, each useful part of the <I>from-space</I>
is copied to the <I>to-space</I>; the new address of a relocated value
is saved (most often in its old location) in order to update all of the
other values that point to this value.<BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora037.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.8: Rewriting from <I>from-space</I> into <I>to-space</I>.</DIV><BR>

<A NAME="fig-sc-copie"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>The contents of the rewritten cells gives new roots. As long as there
are unprocessed roots the algorithm continues.<BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora038.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.9: New roots.</DIV><BR>

<A NAME="fig-sc-copie-suite"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>In the case of sharing, in other words, when attempting to relocate a
value that has already been relocated, it suffices to use the new
address.<BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora039.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.10: Sharing.</DIV><BR>

<A NAME="fig-sc-partage"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>At the end of garbage collection, all of the roots are updated to point
to their new addresses. Finally, the roles of the two parts are reversed
for the next garbage collection.<BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora040.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.11: Reversing the two parts.</DIV><BR>

<A NAME="fig-sc-inv"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>The principal characteristics of this garbage collector are the
following:
<UL>
<LI>
 it depends solely on the size of the objects to be kept;

<LI> only half of the memory is available;

<LI> it compacts memory;

<LI> it may localize values (using breadth-first traversal);

<LI> it does not use extra memory (only <I>from-space</I>+<I>to-space</I>);

<LI> the algorithm is not recursive;

<LI> it relocates values into the new part of memory;
</UL><A NAME="toc120"></A>
<H3> Other Garbage Collectors</H3>
Many other techniques, often derived from the two preceding, have been
used: either in particular applications, e.g., the manipulation of
large matrices in symbolic calculations, or in a general way linked to
compilation techniques. Generational garbage collectors allow
optimizations based on the age of the values. Conservative garbage
collectors are used where there is not an explicit differentiation between immediate
values and pointers (for example, when one translates into C).
Finally, incremental garbage collectors allow us to avoid a noticeable
slow-down at the time of garbage collection activation.<BR>
<BR>

<H4> Generational Garbage Collection</H4>
<A NAME="sec-GC-gen"></A>
<A NAME="@concepts196"></A>
Functional programs are, in general, programs that allocate frequently.
We notice that a very large number of values have a very short
lifetime<A NAME="text21" HREF="book-ora093.html#note21"><SUP><FONT SIZE=2>2</FONT></SUP></A>.
On the other hand, when a value has survived several garbage
collections, it is quite likely to survive for a while longer.
In order to avoid complete traversal of the heap---as in <I>Mark</I>&amp;<I>Sweep</I>---during
each memory reclamation, we would like to be able to traverse only
the values that have survived one or more garbage collections. Most
frequently, it is among the young values that we will recover the most
space. In order to take advantage of this property, we give objects
dates, either a time-stamp or the number of garbage collections
survived. To optimize garbage collection, we use different algorithms
according to the age of the values:
<UL>
<LI>

The garbage collections for young objects should be fast and traverse only
the younger generations.

<LI>
The garbage collections for old objects should be rare and do well at
collecting free space from the entire memory.
</UL>
As a value ages it should take part less and less in the most frequent garbage
collections. The difficulty, therefore, is taking count of only the
region of memory occupied by young objects. In a purely functional
language, that is, a language without assignment, younger objects reference older objects, and on the other hand, older
objects do not possess pointers to younger objects because they were
created before the young objects existed. Therefore, these garbage
collection techniques lend themselves well to functional languages, with
the exception of those with delayed evaluation which can in fact
evaluate the constituents of a structure after evaluating the structure
itself. On the other hand, for functional languages with assignment it
is always possible to modify part of an older object to refer to a
younger object. The problem then is to save young memory regions
referenced only by an older value. For this, it is necessary to keep an
up-to-date table of references from old objects to young objects in
order to have a correct garbage collection. We study the case of
Objective CAML in the following section.<BR>
<BR>

<H4> Conservative Garbage Collectors</H4>
<A NAME="sec-rac-ambig"></A>
<A NAME="@concepts197"></A>
<A NAME="@concepts198"></A>
To this point, all of the garbage collection techniques presume knowing
how to tell a pointer from an immediate value. Note that in functional
languages with parametric polymorphism values are uniformly represented,
and in general occupy one word of memory<A NAME="text22" HREF="book-ora093.html#note22"><SUP><FONT SIZE=2>3</FONT></SUP></A>.
This is what allows having generic code for polymorphic functions.<BR>
<BR>
However, this restriction on the range for integers may not be
acceptable. In this case, conservative garbage collectors make it
possible to avoid marking immediate values such as integers. In this
case, every value uses an entire memory word without any tag bits. In order
to avoid traversing a memory region starting from a root actually
containing an integer, we use an algorithm for discriminating between
immediate values and pointers that relies on the following observations:
<UL>
<LI>
 the addresses of the beginning and end of the heap are known so
 any value outside of these bounds is an immediate value;

<LI> allocated objects are aligned on a word address. Every value that
does not correspond to such an alignment must also be an immediate value.
</UL>
Thus each heap value that is valid from the point of view of being an
address into the heap is considered to be a pointer and the garbage
collector tries to keep this region, including those cases where the
value is in fact an immediate value. These cases may become very rare
by using specific memory pages according to the size of the objects.
It is not possible to guarantee that the entire unused heap is
collected. This is the principal defect of this technique. However, we
remain certain that only unused regions are reclaimed.<BR>
<BR>
In general, conservative garbage collectors are conservative,
i.e., they do not relocate objects. Indeed, as the garbage
collector considers some immediate values as pointers, it would be
harmful to change their value. Nevertheless, some refinements can be
introduced for building the sets of roots, which allow to relocate
corresponding to clearly known roots.
<BR>
<BR>
Garbage collection techniques for ambiguous roots are often used when
compiling a functional language into C, seen here as a portable
assembler. They allow the use of immediate C values coded in a
memory word.<BR>
<BR>

<H4> Incremental Garbage Collection</H4>
<A NAME="@concepts199"></A>
One of the criticisms frequently made of garbage collection is that
it stops the execution of a running program for a time that is
perceptible to the user and is unbounded.
The first is embarrassing in certain applications, for instance,
rapid-action games where the halting of the game for a few seconds is
too often prejudicial to the player, as the execution restarts without
warning. The latter is a source of loss of control for applications
which must process a certain number of events in a limited time. This
is typically the case for embedded programs which control a physical
device such as a vehicle or a machine tool. These
applications, which are real-time in the sense that they must respond in
a bounded time, most often avoid using garbage collectors.<BR>
<BR>
Incremental garbage collectors must be able to be interrupted during any
one of their processing phases and be able to restart while assuring the
safety of memory reclamation. They give a sufficiently satisfactory method
for dealing with the former case, and can be used in the latter case by
enforcing a programming discipline that clearly isolates the software
components that use garbage collection from those that do not.<BR>
<BR>
Let us reconsider the <I>Mark</I>&amp;<I>Sweep</I> example and see what adaptations are
necessary in order to make it incremental. There are
essentially two:
<OL type=1>
<LI>
 how to be sure of having marked everything during the marking phase?

<LI> how to allocate during either the marking phase or the reclamation phase?
</OL>If <I>Mark</I>&amp;<I>Sweep</I> is interrupted in the <I>Mark</I> phase, it is necessary to assure
that cells allocated between the interruption of marking and its restart
are not unduly reclaimed by the <I>Sweep</I> that follows. For this, we
mark cells allocated during the interruption in black or gray in
anticipation.<BR>
<BR>
If the <I>Mark</I>&amp;<I>Sweep</I> is interrupted during the <I>Sweep</I> phase, it can continue
as usual in re-coloring the allocated cells white. Indeed, as the
<I>Sweep</I> phase sequentially traverses the heap, the cells allocated
during the interruption are localized before the point where the sweep
restarts, and they will not be re-examined before the next garbage
collection cycle.<BR>
<BR>
Figure <A HREF="book-ora086.html#fig-ms-incr">9.12</A> shows an allocation during the reclamation phase.
The root <TT>w</TT> is created by:


<PRE><BR># <B>let</B><CODE> </CODE>w<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>'f'</CODE>::v;;<BR><CODE>val w : char list = ['f'; 'z'; 'a'; 'm']</CODE><BR>

</PRE>

<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora041.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 9.12: Allocation during reclamation.</DIV><BR>

<A NAME="fig-ms-incr"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE><HR>
<A HREF="book-ora085.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora087.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
